package practice_list;
/**
 * Created with Intellij JDEA
 * Description:
 * User:
 * Date:2022-04-04
 * Time:12:38
 */
public class 有序链表转换二叉搜索树 {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return buildTree(head,null);
    }
    public TreeNode buildTree(ListNode left,ListNode right){
        if(left == right) {
            return null;
        }
        ListNode mid = findMid(left,right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode findMid(ListNode left,ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
